package day25;

import java.util.Scanner;

/**
 * 题目：星际密码
 * 题目链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?
 * 斐波那契额数列变形
 */
public class Main1 {
    public static void main(String[] args) {
        int[] nums = new int[10001];
        nums[1] = 1;
        nums[2] = 2;
        for (int i = 3; i < nums.length ; i++) {
            nums[i] = nums[i-1]+nums[i-2];
            //取最后四位数字
            nums[i] = nums[i] % 10000;
        }
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            StringBuilder sb = new StringBuilder("") ;
            for (int i = 0; i < n; i++) {
                int xi = scanner.nextInt();
                sb.append(String.format(("%04d"),nums[xi]));
            }
            System.out.println(sb);
        }
    }
}
